import java.util.ArrayList;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: ws
 * Date: 2024-01-21
 * Time: 23:30
 *
 * https://www.nowcoder.com/share/jump/7745334641705851140622
 */
public class BM98 {
    ArrayList<Integer> res;

    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        res = new ArrayList<>();
        // 排除 null 和 数组为空的情况
        if (matrix == null || matrix.length == 0) {
            return res;
        }
        int row = matrix.length, col = matrix[0].length;
        // 定位，左上角为(x1, y1)，右下角为(x2, y2)
        int x1 = 0, y1 = 0;
        int x2 = row - 1, y2 = col - 1;
        // 顺时针遍历外圈，然后不停递归
        circle(matrix, x1, y1, x2, y2);
        // 返回结果
        return res;
    }
    // 遍历 以 (x1, y1) 作为左上角，(x2, y2) 作为右下角形成的「圈」
    void circle(int[][] matrix, int x1, int y1, int x2, int y2) {
        // 递归出口，当两个点位置交换
        if (x1 > x2 || y1 > y2) {
            return;
        }
        // 仅仅只有一行，遍历完结束
        if (x1 == x2) {
            for (int i = y1; i <= y2; i++) {
                res.add(matrix[x1][i]);
            }
            return;
        }
        // 仅仅只有一列，遍历完结束
        if (y1 == y2) {
            for (int i = x1; i <= x2; i++) {
                res.add(matrix[i][y1]);
            }
            return;
        }
        // 上
        for (int i = y1; i < y2; i++) {
            res.add(matrix[x1][i]);
        }
        // 右
        for (int i = x1; i < x2; i++) {
            res.add(matrix[i][y2]);
        }
        // 下
        for (int i = y2; i > y1; i--) {
            res.add(matrix[x2][i]);
        }
        // 左
        for (int i = x2; i > x1; i--) {
            res.add(matrix[i][y1]);
        }
        // 递归下一圈，两个点的范围小一圈
        circle(matrix, x1 + 1, y1 + 1, x2 - 1, y2 - 1);
    }
}
